package com.atguigu.recursion;

import java.util.Arrays;

public class NewEightQueenDemo {
    public static void main(String[] args) {
        NewEightQueen newEightQueen = new NewEightQueen();
        newEightQueen.pushQueen(0);
        newEightQueen.printStaticInfo();

    }
}

/**
 * 新八皇后的解决思路,也是官方的解决思路
 * 在此解决思路中,成功结束点不止一个
 *
 * 另外,递归不一定是回溯算法, 回溯算法一定会用到递归
 * 回溯算法中的回溯,指的就是遇到失败信息, 而回溯. 此处的回溯, 不止要考虑到最终的回溯, 还需要考虑到进行到某一步骤就进行不下去了, 因此而回溯. 这是手写板的失误之一.
 *
 */
class NewEightQueen{
    private final int[] queens=new int[8];
    private int count=0;
    private int judgeCount=0;

    public boolean judge(int nextRow,int nextCol){
        judgeCount++;
        for (int oldRow = 0; oldRow < nextRow; oldRow++) {
            int oldCol = queens[oldRow];
            if (oldCol==nextCol||Math.abs(oldRow-nextRow)==Math.abs(oldCol-nextCol)) {
                return false;
            }
        }
        return true;
    }

    public void pushQueen(int row){
        // 成功结束点
        if (row==8) {
            record();
            return;
        }
        /*
         * 中继点候选项. 由于要吧所有成功结果均记录, 故遇到成功信息点不再一路返回, 而是先回溯到上一节点, 再走同一栈的下一候选项.
         * 最大可能中继点数量=每个递归栈的候选分支数^最大递归栈数  => 实际不一定能手动求出来
         * 在这里, 就是8^8次. 尽管由于回溯判断(judge), 导致实际中继点数(15720)远小于此值, 回溯算法仍是一个比较消耗性能的算法.
         * 如果要使用回溯算法, 应考虑如下:
         * 1. 尽量较少候选分支数
         * 2. 尽量减少最大递归栈数(重要!!!)
         * 3. 优化回溯判断
         *
         * 此外, 目前看, 共有两种处理中继递归点的思路.
         * 1. 将中继递归点, 作为判断是否回溯的原因. 如迷宫确定路线. 暂命名为逆向递归回溯(?), 通常成功结果只能有一个
         * 2. 将中继递归点, 作为不需要回溯的结果. 如八皇后. 暂命名为正向递归回溯. 成功结果允许有多个.
         * 共同之处是:
         * 成功结束点都在最后才能确定
         * 失败结束点需要在任何时候都能确定.
         */
        for (int col = 0; col < 8; col++) {
            queens[row]=col;
            if (judge(row,col)) {
                // 当前中继点成功, 继续下一个递归栈
                pushQueen(row+1);
            }
            // 此处相当于是, 如果失败了,则直接pass
        }
    }

    public void record(){
        count++;
        System.out.println(Arrays.toString(queens));
    }

    public void printStaticInfo(){
        System.out.printf("共找到%d个解\n",count);
        System.out.printf("共判断%d次",judgeCount);
    }
}
